package huawei.checkandset;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class J128 {
    int[] parents;
    int[] ranks;

    public static void main(String[] args){
        System.out.println(new J128().longestConsecutive(new int[]{100,4,200,1,3,2}));
    }
    public int longestConsecutive(int[] nums) {
        ArrayList<Integer> data = new ArrayList<>();
        for (int num :
                nums) {
            if(!data.contains(num)){
            data.add(num);}
        }
        parents=new int[data.size()];
        ranks=new int[data.size()];
        for (int i = 0; i < data.size(); i++) {
            parents[i]=i;
            ranks[i]=1;
        }
        boolean[] visited=new boolean[data.size()];
        for (int i = 0; i < data.size(); i++) {
            if(visited[i]){
                continue;
            }
            for (int m = i+1; m < data.size(); m++) {
                if(Math.abs(data.get(i)-data.get(m))==1){
                    merge(i,m);
                }
            }
            visited[i]=true;
        }
        int max =0;
        for (int i = 0; i < parents.length; i++) {
            if(parents[i]==i){
                max=Math.max(max,ranks[i]);
            }
        }
        return max;
    }

    int find(int i){
        if(parents[i]==i){
            return i;
        }
        return find(parents[i]);
    }
    void merge(int a, int b){
        int rootA= find(a);
        int rootB=find(b);
        if(rootA==rootB){
            return ;
        }
        if(ranks[rootA]<ranks[rootB]){
            parents[rootA]=rootB;
            ranks[rootB]+=ranks[rootA];
        }else {
            parents[rootB]=rootA;
            ranks[rootA]+=ranks[rootB];
        }
    }
    public int longestConsecutive2(int[] nums) {
        if(nums.length<=0)return 0;
        Arrays.sort(nums);
        int len =1;
        int max =1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]-nums[i-1]==1){
                len++;
            }else if(nums[i]-nums[i-1]==0){
                continue;
            }
            else{
                max = max>len?max:len;
                len=1;
            }
        }
        max = Math.max(max, len);
        return max;
    }

}
